package com.zwh.algorithm.leetcode.medium;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class LeetCode24 {
    /**
     * 2023-08-06 两两交换链表中的节点
     * todo 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     *  输入：head = [1,2,3,4]
     *  输出：[2,1,4,3]
     * @param args
     */
    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(4,node1);
        ListNode node3 = new ListNode(2,node2);
        ListNode node4 = new ListNode(7,node3);
        ListNode node = swapPairs(node4);
        while (node != null){
            System.out.println(node.val);
            node = node.next;
        }

    }
    public static ListNode swapPairs(ListNode head) {
        List<ListNode> list = new ArrayList();
        while (head != null){
            list.add(head);
            head = head.next;
        }
        int len = list.size();
        if (len == 0){
            return head;
        }else if (len == 1){
            return list.get(0);
        }
        for (int i = (len % 2 == 1) ? len - 2 : len -1; i > 0; i-=2) {
            ListNode listNode = list.get(i);
            list.set(i,list.get(i-1));
            list.set(i -1,listNode);
        }
        for (int i = 0; i < len -1; i++) {
            list.get(i).next = list.get(i+1);
        }
        list.get(len -1).next =null;
        return list.get(0);
    }

    /**
     * 递归
     * @param head
     * @return
     */
    public ListNode swapPairs1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }

    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
